package leetcode.L500;

import java.util.HashMap;

public class EX106 {
    //方法一

//    int[] postorder;
//    int pos_idx;
//    HashMap<Integer,Integer> map = new HashMap<>();
//
//
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        this.postorder = postorder;
//
//        int idx = 0;
//        for(Integer val : inorder)
//            map.put(val,idx++);
//        pos_idx = postorder.length-1;
//        return help(0,postorder.length-1);
//
//    }
//
//    private TreeNode help(int left,int right){
//        if(left>right)
//            return null;
//        int idx = map.get(postorder[pos_idx]);
//        pos_idx--;
//        TreeNode root = new TreeNode(postorder[pos_idx]);
//        root.right = help(idx+1,right);
//        root.left = help(left,idx-1);
//        return root;
//    }
    //方法二

    int[] postorder;
    HashMap<Integer,Integer> map = new HashMap<>();


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;

        int idx = 0;
        for(Integer val : inorder)
            map.put(val,idx++);
        return help(0,inorder.length-1,0,postorder.length-1);

    }

    private TreeNode help(int inleft,int inright,int posleft,int posright){
        if(inleft>inright)
            return null;
        int idx = map.get(postorder[posright]);

        TreeNode root = new TreeNode(postorder[posright]);
        root.right = help(idx + 1,inright,posright-(inright-idx),posright-1);
        root.left = help(inleft,idx-1,posleft,posright-(inright-idx)-1);
        return root;
    }




}

